package com.zlp.partice;

import com.sun.javafx.collections.MappingChange;
import org.junit.Test;

import java.io.FileOutputStream;
import java.util.*;

/**
 * @author zhulaiping
 * @date 2021/6/25-10:19
 */
public class Day20210625 {

    @Test
    public void tt(){
        openLock(new String[]{"8888"},"0009");
    }

    public int openLock(String[] deadends, String target) {
        Set<String> set = new HashSet<>(Arrays.asList(deadends));
        if(set.contains("0000")) return -1;
        Queue<String> queue = new LinkedList<>();
        queue.add("0000");
        int step = 0;
        while (!queue.isEmpty()){
            int len = queue.size();
            for (int i=0;i<len;i++){
                String curStr = queue.poll();
                if(curStr.equals(target)) return step;
                for (int j=0;j<4;j++){
                    char[] chars = curStr.toCharArray();
                    chars[j] += 1;
                    if(chars[j]==58) chars[j] = 48;
                    String s1 = new String(chars);
                    if(!set.contains(s1)){
                        set.add(s1);
                        queue.offer(s1);
                    }
                    char[] chars2 = curStr.toCharArray();
                    chars2[j] -= 1;
                    if(chars2[j]==47) chars2[j] = 57;
                    String s2 = new String(chars2);
                    if(!set.contains(s2)){
                        set.add(s2);
                        queue.offer(s2);
                    }

                }
            }
            step++;
        }
        return -1;
    }


    public int minAbsoluteSumDiff(int[] n1, int[] n2) {
        int mod = (int) (1e9+7);
        int len = n1.length;
        int[] copy = new int[len];
        System.arraycopy(n1,0,copy,0,len);
        Arrays.sort(copy);
        int sum = 0,max = 0;
        for (int i=0;i<len;i++){
            int cur = cal(copy,n2[i]);
            int abs = Math.abs(n1[i]-n2[i]);
            max = Math.max(max,abs-cur);
            sum = (abs+sum)%mod;
        }
        return (sum - max + mod)%mod;
    }

    private int cal(int[] copy, int i) {
        int cur = Integer.MAX_VALUE;
        int l = 0,r = copy.length-1;
        while (l<=r){
            int mid = l+(r-l>>1);
            if(copy[mid]==i) return 0;
            else if(copy[mid]<i){
                l = mid + 1;
            }else {
                r = mid - 1;
            }
            cur = Math.min(cur,Math.abs(copy[mid]-i));
        }
        return cur;
    }
    public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
        Arrays.sort(arr);
        int len = arr.length;
        for (int i=1;i<len;i++){
            if(arr[i]-arr[i-1]>1){
                arr[i] = arr[i-1]+1;
            }
        }
        return arr[len-1];
    }

    public int maxSubArray(int[] nums) {
        int len = nums.length,sum=-101;
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i=1;i<dp.length;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            sum = Math.max(sum,dp[i]);
        }
        return sum;
    }

    public int search(int[] nums, int target) {
        int l = 0,r = nums.length-1,ret = 0;
        while (l<=r){
            int mid = l+(r-l>>1);
            if(nums[mid]<target) l = mid+1;
            else if(nums[mid]>target) r = mid-1;
            else {
                int m = mid+1,n=mid-1;
                ret = 1;
                while (nums[m++]==target) ret++;
                while (nums[n--]==target) ret++;
            }
        }
        return ret;
    }

    @Test
    public void se(){
        groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
    }
    public List<List<String>> groupAnagrams(String[] strs) {
        int len = strs.length;
        List<List<String>>ret = new ArrayList<>();
        Map<Map<Character,Integer>,List<String>>pos = new HashMap<>();
        for (String s:strs){
            Map<Character,Integer> map = new HashMap<>();
            count(s,map);
            List<String> list = pos.getOrDefault(map, new ArrayList<>());
            list.add(s);
            pos.put(map,list);
        }
        for (Map.Entry<Map<Character,Integer>,List<String>> entry:pos.entrySet())
            ret.add(entry.getValue());
        return ret;
    }
    private void count(String str, Map<Character,Integer> map) {
        for (char ch:str.toCharArray()){
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
    }

    public int maxFrequency(int[] nums, int k) {
        int ret = 1,l = 0;
        long temp = k;
        Arrays.sort(nums);
        for (int r=1;r<nums.length;r++){
            temp -= (long) (nums[r]-nums[r-1])*(r-l);
            while (temp<0){
                temp += nums[r]-nums[l];
                l++;
            }
            ret = Math.max(ret,r-l+1);
        }
        return ret;
    }
    public List<Integer> pathInZigZagTree(int label) {
        int[] map = new int[21];
        for (int i=0;i<20;i++) {
            map[i] = 1 << i;
        }
        LinkedList<Integer>ret = new LinkedList<>();
        ret.add(label);
        while (label!=1){
            label /= 2;
            for (int i=1;i<map.length;i++){
                if(label>=map[i-1]&&label<map[i]){
                    ret.addFirst(map[i-1]+map[i]-1-label);
                    break;
                }
            }
        }
        return ret;
    }


}
